package org.simtube.cluster;

import java.util.ArrayList;

import org.simtube.util.*;
import org.simtube.preprocess.*;

class KMeans {
	
	private Clustering data;
	
	KMeans(Clustering c)
	{
		this.data = c;
	}
	
	/**
	 * Perform clustering on given array of doc id using K-means.
	 * K will be determined automatically.
	 * @param docs  the array of doc id
	 * @return   A list, each element is an array of doc id in one cluster
	 */
	protected ArrayList<Cluster> cluster(int[] docs, int k)
	{
		if (k == -1)  // get k automatically
		{
			return null;
		}
		else
		{
			ArrayList<Integer> ran = new ArrayList<Integer>();
			DocVector[] centers = new DocVector[k];
			int i, t;
			ran.clear();
			for (i = 0; i < docs.length; i++) ran.add(docs[i]);
			for (i = 0; i < k; i++)
			{
				t = (int)(Math.random() * ran.size());
				centers[i] = data.getDvectors()[ran.get(t)].vector;
				ran.remove(t);
			}
			return this.cluster(docs, k, centers, true);
		}
	}

	/**
	 * Perform clustering on given array of doc id using K-means
	 * @param docs  the array of doc id
	 * @param k   the number of clusters
	 * @param centers   initial centers of clusters
	 * @return   A list, each element is an array of doc id in one cluster
	 */
	private ArrayList<Cluster> cluster(int[] docs, int k,
			DocVector[] centers, boolean getTag)
	{
		int i, j, t;
		boolean changed;
		int[] flags = new int[docs.length];
		for (i = 0; i < flags.length; i++) flags[i] = -1;
		
		// clustering
		double temp, max;
		DocVector c, v;
		int[] counts = new int[k];
		changed = true;
		while (changed)
		{
			// classify
			changed = false;
			for (i = 0; i < docs.length; i++)
			{
				t = flags[i];
				max = 0;
				v = data.getDvectors()[docs[i]].vector;
				if (flags[i] != -1)
					max = v.multiply(centers[flags[i]]) 
						/ centers[flags[i]].norm();
				for (j = 0; j < k; j++)
				{
					if (j == flags[i]) continue;
					c = centers[j];
					temp = c.multiply(v) / c.norm();
					if (flags[i] == -1 || temp > max)
					{
						max = temp;
						flags[i] = j;
						changed = true;
					}
				}
			}
			
			// calculate new centers
			for (i = 0; i < k; i++)
			{
				counts[i] = 0;
				centers[i] = centers[i].multiply(0);
			}
			for (i = 0; i < docs.length; i++)
			{
				v = data.getDvectors()[docs[i]].vector;
				t = flags[i];
				counts[t]++;
				centers[t] = centers[t].add(v);
			}
			for (i = 0; i < k; i++)
				centers[i] = centers[i].multiply(1.0 / counts[i]);
		}
		
		// getting result
		ArrayList<Cluster> result = new ArrayList<Cluster>();
		result.clear();
		for (i = 0; i < k; i++)
		{
			result.add(new Cluster(counts[i]));
			counts[i] = 0;
		}
		for (i = 0; i < docs.length; i++)
		{
			t = flags[i];
			result.get(t).getDocItems()[counts[t]] = i;
			counts[t]++;
		}
		
		if (!getTag) return result;
		
		// getting tags
		FilePreprocess f = data.getFilePreprocess();
		ArrayList<ArrayList<TermTFIDF>> cdata;
		cdata = new ArrayList<ArrayList<TermTFIDF>>();
		for (i = 0; i < result.size(); i++)
			cdata.add(new ArrayList<TermTFIDF>());
		/*
		 *  cdata is temporarily used for statistics.
		 *  TermTFIDF.termIndex = index of term
		 *  TermTFIDF.tf = tf in a cluster
		 */
		ArrayList<TermTFIDF> d, tfcounts;
		TermTFIDF tempt;
		Cluster cl;
		for (j = 0; j < result.size(); j++)
		{
			cl = result.get(j);
			for (i = 0; i < cl.getDocItems().length; i++)
			{
				d = f.getDocTFIDF("data/tf/" + this.data.getDvectors()
						[cl.getDocItems()[i]].index);
				for (TermTFIDF term : d)
				{
					tempt = isIn(cdata.get(j), term);
					if (tempt == null)
					{
						tempt = new TermTFIDF(term.getTermIndex(), 0, 0);
						tempt.setTF(term.getTF());
						cdata.get(j).add(tempt);
					}
					else tempt.setTF(tempt.getTF() + term.getTF());
				}
			}
		}
		double rank, rmax = 0;
		int tag = -1;
		tfcounts = new ArrayList<TermTFIDF>();
		for (ArrayList<TermTFIDF> l : cdata) {
			for (TermTFIDF term : l) {
				tempt = isIn(tfcounts, term);
				if (tempt == null)
				{
					tempt = new TermTFIDF(term.getTermIndex(), 0, 0);
					tempt.setTF(term.getTF());
					tfcounts.add(tempt);
				}
				else tempt.setTF(tempt.getTF() + term.getTF());
			}
		}
		for (i = 0; i < result.size(); i++) {
			ArrayList<TermTFIDF> l = cdata.get(i);
			rmax = 0;
			tag = -1;
			for (TermTFIDF term : l) {
				tempt = isIn(tfcounts, term);
				rank = term.getTF() / tempt.getTF();
				if (rank > rmax)
				{
					rmax = rank;
					tag = term.getTermIndex();
				}
			}
			result.get(i).setTag(tag);
		}
		return result;
	}
	
	private TermTFIDF isIn(ArrayList<TermTFIDF> l, TermTFIDF t)
	{
		for (TermTFIDF termTFIDF : l)
			if (termTFIDF.getTermIndex() == t.getTermIndex())
				return termTFIDF;
		return null;
	}
}
